package offer;

import java.util.LinkedList;
import java.util.Queue;


/**
 * @Author SSK
 * @Date Created in 0:11 2019/8/9
 * @Description 机器人的运动范围
 * @Version 1.0
 */
public class T67 {

    final static int[][] WZ = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    public int movingCount(int threshold, int rows, int cols) {
        if (threshold<0) {
            return 0;
        }
        boolean vis[][] = new boolean[rows][cols];
        for (int i = 0; i < vis.length; i++) {
            vis[i] = new boolean[cols];
            for (int i1 = 0; i1 < vis[i].length; i1++) {
                vis[i][i1] = false;
            }
        }
        class Point{
            int x;
            int y;

            public Point(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
        Queue<Point> queue = new LinkedList<Point>();
        int ans = 0;
        queue.add(new Point(0,0));
        vis[0][0] = true;
        while (!queue.isEmpty()) {
            Point u = queue.poll();
            ans++;
            for (int i = 0; i < WZ.length; i++) {
                int x = u.x + WZ[i][0];
                int y = u.y + WZ[i][1];
                if (x>=0&&y>=0&&x<rows&&y<cols&&!vis[x][y]&&(getNum(x)+getNum(y)<=threshold)) {
                    vis[x][y] = true;
                    queue.add(new Point(x,y));
                }
            }
        }
        return ans;
    }
    public int getNum(int num) {
        int ans = 0;
        while (num>0){
            ans += num%10;
            num/=10;
        }
        return ans;
    }
    public static void main ( String[] args) {
       System.out.print(new T67().movingCount(5,10,10));

    }

}
